/**
 * 这是一个链表
 */
public class MySingleList {
    static class Node{  // 是不是静态内部类就看自己需求了
        // 以为节点是链表组成的一部分，节点也是一个类
        // 需要把节点定义成一个内部类
        public int val; // 存储数据
        public Node next; // 存储下一个节点的地址

        // 设置成静态类的好处就是，如果在类外还需要使用这个类的话。呢就不需要对象了 ， 生成Node对象的时候不依赖外部对象
        public Node(int val){
            this.val = val;  // 数据可以先构造
            // 不给next
            // 因为一开始根本就不知到next是谁
            // 需要用逻辑实现

        }
    }
    // 接下来创建head对象
    public Node head; // 代表当前链表的头节点
    // 看head引用谁了


    //创建一个链表,假设有四个节点
    public void createLink(){
        // 四个节点 ，
        Node node1 = new Node(12);
        Node node2 = new Node(45);
        Node node3 = new Node(23);
        Node node4 = new Node(90);

        //给next赋值
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }

    // 首先遍历链表
    public void display(){
        // 从head开始往后遍历
        Node cur = head;
        // 问题是head怎么往后走
        while( /*head != null*/  cur !=  null ){  // 条件是head！=null ， 如果是head.next ！= null 会少打印一个
            // 但是如果说是 head != null 那么最后你会发现 头节点找不到了，头节点为null了现在 ， 打印两次只有一次的结果
            // 所以要在定义一个变量 cur ， 让cur来动
           // System.out.print(head.val+" ");
            System.out.print(cur.val+" ");
            //head = head.next; // head往后走
            cur = cur.next;
        }
        // 结论： 如果说 把整个链表遍历完成 则是 head == null
        //       如果说 只遍历到链表的尾巴 则是 head.next == null
        System.out.println();
    }

    // 从指定位置打印链表
    public void display(Node newHead){
        Node cur = newHead;
        while( /*head != null*/  cur !=  null ){ 
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    //下面两个是学完栈之后来写的
    //递归打印链表
    public void display2(Node pHead){
        if(pHead == null){
            return;
        }
        if(pHead.next == null){
            System.out.println(pHead.val+" ");
            return;
        }
        //其余情况，来递归调用
        display2(pHead.next);
        System.out.println(pHead.val+" ");//每次回来的时候把没有递归的递归完
    }
    //用栈的形式打印链表
    public void display2(Node pHead){
        Stack<Node> stack = new Stack<>();
        //首先遍历链表
        Node cur = head;
        while (cur != head){
            stack.push(cur);
            cur = cur.next;
        }
        //遍历栈并打印
        while(!stack.isEmpty()){
            Node top =  stack.pop();
             System.out.print(top.val+" ");
        }
        System.out.println();
    }

    //查找是否包含关键字key是否在链表当中
    public boolean contains(int key){
        // 需要从头去遍历这个链表
        Node cur = head;
        while(cur!=null){
            if(cur.val == key){  // 这个因为val是int类型的所以用 ==
                // 如果是引用类型的话不能用等号了，要用 .equals()
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    // 得到链表的长度  //时间复杂度是O(N)
    public int size(){
        int count = 0;
        Node cur = head;
        while(cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    //头插法
    // 意思就是把一个新节点插入到当前列表的头部

    // 插入数据
    // 1.得有节点
    // 2.要修改两个地方 ， 新节点的next的值要改， 之前的head的值要改
    public void addFirst(int data){
        Node node = new Node(data); // 建立新节点
        /*
        head = node;
        node.next = head ;
        * */  // 这样写是错误的，写反了，这个是自己指向自己
        // 应该这样写
         node.next = head;
         head = node;
         // 应该先绑后面然后再管其他的
    }

    //尾插法
    // 把节点插入到该链表的尾部
    // 需要修改 最后一个节点的next的值，再改新节点的next的值
    public void addLast(int data){
        Node node = new Node(data);
        // 如何找到最后一个节点的值
        // 需要定义一个cur
        // 先判断head是否为null
        if(head == null){
            head = node;
            return;
        }
        Node cur = head;
        while(cur.next!=null){  //找到最后一个节点的位置
            cur = cur.next;
        }
        cur.next = node;
        //但是head如果是null的话
        // 拿这个代码插入是错误的
        // 应该再这样写先判断head是否为空
    }
    // 总结：链表 的插入只是修改指向


    //任意位置插入，第一个数据节点为0号的下标
    //则是将前一个节点的next值改成这个新节点的值
    // 再将这个新节点的next值改成后一个节点的值
    // 那么如何找到要插入的该位置呢
    // 就是要往哪一个位置插就让cur走到呢个位置的前一个节点 index-1
    // node.next = cur.next;
    // cur.next = node;
    // 关键就是要找到cur
    public  void addIndex(int index,int data){
        Node node = new Node(data);
        //先检查index
        checkIndex(index);
        //再判断index的值
        if (index == 0){
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return;
        }
        //考虑中间值
        /*Node cur = head;
        int count = 0;
        while(count!=index-1) {
            cur = cur.next;
            count++;
        }*/
        //将这一段用一个方法来表示
        Node cur = findIndexSubOne(index);
        node.next = cur.next;  // 一定要先绑后面的
        cur.next = node;
    }
    // 然后判断index是否合法
    private  void checkIndex(int index) throws IndexOutOfException{
        if(index<0||index>size()){
            throw new IndexOutOfException("index位置不合法");
        }
    }
    //考虑中间值

    /**
     * 找到index-1位置节点的地址
     * @param index
     * @return
     */
    public Node findIndexSubOne(int index){
        Node cur = head;
        int count = 0;
        while(count!=index-1){
            cur = cur.next;
            count++;
        }
        return cur;
    }


    //删除第一次出现关键字为key的节点
    // 删除该节点就是跳过该节点
    //将该节点前一个节点的地址直接换成指向后面节点的地址
    // 所以cur要走到删除节点的前一个地方
    // cur.next = del.next;  或者 cur.next = cur.next.next;  // 这个代码不影响最后一个节点
    // 但是删除第一个元素也是一个问题，第一个元素没有前驱
    // 所以先判断head需不需要删除
    //

    public void remove(int key){

        //先判断头节点是否要删除
        if(head.val == key){
            head = head.next;
            return;
        }
        //接下来找到要删除节点的前一个节点
        Node cur = searchPrey(key); // 代表当前的节点
        if (cur == null){
            return;
        }
        Node del = cur.next;// 代表要删除的节点
        cur.next = del.next;
    }
    //接下来找到要删除节点的前一个节点

    /**
     * 找到关键字key的前一个节点
     * @param key
     * @return
     */
    private  Node searchPrey(int key){
        //要判断head 是否为null
        if (head == null){
            return null; // 一个节点都没有
        }
        Node cur = head;
        while(cur.next != null){ //cur.next.val 代表要删除节点位置的数据，而此时的cur还是指向前一个节点的位置
            // 要考虑key是否在链表种能够找到
            //**** 当cur.next == null 时说明没有找到 ****
            if (cur.next.val == key){
                return cur;
            }
            cur = cur.next;

        }
        return null; //代表没有你要删除的节点
    }


    //删除所有key的节点
    // 定义一个cur ，定义一个prev
    // cur代表当前节点是否要被删除
    // prev记录cur的位置
    public void removeAllKey(int key){
        if (head == null){
            return;
        }
        Node prev = head;
        Node cur = head.next;
        while(cur != null){
            if(cur.val == key){
                prev.next = cur.next;
                cur = cur.next; // 让cur往后走，prev不动
            }else{
                prev = cur;//不等于的话，让prev走到cur的位置
                cur=cur.next;//之后cur 继续往后走，直到cur == null
            }
        }
        //但是如果prev的位置上也是要删除的目标值的话、
        //值依靠这个 呢就不会被删除
        //所以要进行判断 ， 这个判断如果写在前面几行的话要用while来进行判断
        // 如果时经过删除后，再放后面进行判断的话用if就可以
        if(head.val == key){
            head = head.next;
        }
    }

    //清空链表

    /**
     * 表示链表的每个节点都要被回收
     */
    //只要第一个节点没有被指向的话。剩余的节点都将会被回收
    public void clear(){
        head = null;
    }

    //链表的反转
    public Node reverseList() {
        if(head == null){
            return null;
        }
        /*if(head.next = null){
            return = head;
        }*/
        Node cur = head.next;
        head.next = null;
        while(cur!=null){
            Node next = cur.next;
            cur.next = head;
            head = cur;
            cur = next;
        }
      return head;
    }
}
